package com.ruijixiang.leetcode.weekly.leetcode2024.leetcode20240901;

import java.util.*;

public class leetcode3276 {
    // 记忆化搜索
    public int maxScore(List<List<Integer>> grid){
        Map<Integer,Integer> pos=new HashMap<>();
        int m=grid.size();
        for(int i=0;i<m;i++){
            for(int x : grid.get(i)){
                // 保存所有包含x的行号 (压缩成二进制)
                pos.merge(x,1<<i,(a,b)->a|b);
            }
        }

        // 只考虑在grid中的元素
        List<Integer> allNums=new ArrayList<>(pos.keySet());
        int n=allNums.size();
        int[][] memo=new int[n][1<<m];
        for(int[] row : memo){
            Arrays.fill(row,-1);// -1表示没有计算过
        }
        // dfs(x,y,pos,allNums,memo)
        return dfs(n-1,0,pos,allNums,memo);
    }

    private int dfs(int i,int j,Map<Integer,Integer> pos,List<Integer> allNums,int[][] memo){
        if(i<0){
            return 0;
        }
        if(memo[i][j]!=-1){// 之前按计算过
            return memo[i][j];
        }
        // 不选x
        int res=dfs(i-1,j,pos,allNums,memo);
        // 枚举选第k行的x
        int x=allNums.get(i);
        for(int t=pos.get(x),lb;t>0;t^=lb){
            lb=t & -t;// lb=1<<k，其中k是行号
            if((j & lb)==0){
                res=Math.max(res,dfs(i-1,j | lb,pos,allNums,memo)+x);
            }
        }
        return memo[i][j]=res;// 记忆化
    }
}
